package zifuchuan

func StrStr(haystack string, needle string) int {
	a, b := len(haystack), len(needle)
	if a < b {
		return -1
	}
	x, y := []byte(haystack), []byte(needle)
	for i := 0; i < a-b; i++ {
		match := true
		for j := 0; j < b; j++ {
			if y[j] != x[i+j] {
				match = false
				break
			}
		}
		if match {
			return i
		}
	}
	return -1
}

func StrStr2(haystack string, needle string) int {
	a, b := len(haystack), len(needle)
	if b == 0 {
		return 0 // 按照惯例，空字符串始终匹配开头
	}
	if a < b {
		return -1
	}

	x := []byte(haystack)
	y := []byte(needle)

	for i := 0; i <= a-b; i++ {
		match := true
		for j := 0; j < b; j++ {
			if x[i+j] != y[j] {
				match = false
				break
			}
		}
		if match {
			return i
		}
	}
	return -1
}

func StrKMP(haystack, needle string) int {
	next := GetNext(needle)
	m, n := len(haystack), len(needle)
	i, j := 0, 0
	for i < m {
		if haystack[i] == needle[j] {
			i++
			j++
		}
		if j == n {
			return i - j
		} else if i < m && haystack[i] != needle[j] {
			if j > 0 {
				j = next[j-1]
			} else {
				i++
			}
		}
	}
	return -1
}
func GetNext(needle string) []int {
	n := len(needle)
	next := make([]int, n)
	i := 1
	length := 0
	next[length] = 0
	for i < n {
		// 内部进行处理
		if needle[i] == needle[length] {
			length++
			next[i] = length
			i++
		} else {
			if length != 0 {
				length = next[length-1]
			} else {
				next[i] = 0
				i++
			}
		}
	}
	return next
}
